package com.mc.priority;

/**
 * 最小堆实现的优先队列
 * @author MC
 *
 */
public class MinPQ {
		
	private int[] queue;
	private int count;
	
	public MinPQ(){
		queue = new int[100];
	}
	public int delMin(){
		int max = queue[0];
		queue[0] = queue[count-1];
		count--;
		int k = 0;
		while(k*2+1<count){
			int j = k*2+1;
			if(j+1<count&&queue[j]>queue[j+1])j++;
			if(queue[k]<queue[j])break;
			
			int temp = queue[j];
			queue[j] = queue[k];
			queue[k] = temp;
			k = j;
		}
		return max;
	}
	
	public void insert(int obj){
		queue[count] = obj;
		int k = count;
		while(k>0&&queue[k]<queue[(k-1)/2]){
			int temp = queue[(k-1)/2];
			queue[(k-1)/2]=queue[k];
			queue[k]=temp;
			k = (k-1)/2;
		}
		count++; 
	}
	public static void main(String[] args) {
		MinPQ m = new MinPQ();
		m.insert(1);
		m.insert(5);
		m.insert(3);
		m.insert(10);
		m.insert(0);
		m.insert(2);
		System.out.println(m.delMin());
		System.out.println(m.delMin());
		System.out.println(m.delMin());
		System.out.println(m.delMin());
		System.out.println(m.delMin());
	}
}
